package cn.hycat.leetcode.middle;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*      单调栈 + 哈希表
        nums1中数字的 下一个更大元素 是指在nums2 中对应位置 右侧 的 第一个 比大的元素。
        给你两个 没有重复元素 的数组nums1 和nums2 ，下标从 0 开始计数，其中nums1是nums2的子集。
        对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。
        如果不存在下一个更大元素，那么本次查询的答案是 -1 。
        返回一个长度为nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

        示例 1：

        输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
        输出：[-1,3,-1]
        解释：nums1 中每个值的下一个更大元素如下所述：
        - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
        - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
        - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
        示例 2：

        输入：nums1 = [2,4], nums2 = [1,2,3,4].
        输出：[3,-1]
        解释：nums1 中每个值的下一个更大元素如下所述：
        - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
        - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

        提示：

        1 <= nums1.length <= nums2.length <= 1000
        0 <= nums1[i], nums2[i] <= 104
        nums1和nums2中所有整数 互不相同
        nums1 中的所有整数同样出现在 nums2 中*/
public class L496下一个更大的元素 {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap();
        Stack<Integer> s = new Stack();
        for(int i = 0; i < nums2.length; i++) {
            while(!s.isEmpty() && nums2[i] > nums2[s.peek()]) {
                Integer pop = s.pop();
                map.put(nums2[pop], i); //记录<num2[弹出索引], 比当前值大的下标>
            }
            s.push(i);
        }

        for(int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]) == null ? -1 : nums2[map.get(nums1[i])];
        }

        return res;
    }
}
